1. Field of the Invention (Technical Field)
The present invention relates to hexahedral mesh generation techniques.
2. Background Art
The finite element method is used to simulate a wide variety of physical phenomena, for example heat transfer, structural mechanics, and computational fluid dynamics. In recent years, mesh generation has emerged as one of the major bottlenecks in the simulation process. Although a high degree of automation is available in tetrahedral mesh generators, hexahedral mesh generators still require a great deal of user intervention. Since it is widely believed that hexahedral meshes are more accurate and more robust for some types of finite element analysis, especially in the non-linear regime, these types of meshes are more commonly used.
There has been a great deal of research into automated, all-hexahedral meshing algorithms, e.g., N. T. Folwell, et al., “Reliable Whisker Weaving via Curve Contraction”, Proc. 7th Int. Meshing Roundtable, Sandia National Laboratories, Albuquerque, N. Mex. (October 1998); A. Scheffer, et al., “Hexahedral Mesh Generation Using the Embedded Voronoi Skeletons”, Proc. 7th Int. Meshing Roundtable, Sandia National Laboratories, Albuquerque, N. Mex. (October 1998); and M. Muller-Hannemann, “Hexahedral Mesh Generation by Successive Dual Cycle Elimination”, Proc. 7th Int. Meshing Roundtable, Sandia National Laboratories, Albuquerque, N. Mex. (October 1998), but as yet no algorithm has been found with the key characteristics of high robustness, high mesh quality and low element count. Therefore, current hexahedral mesh generation techniques rely on a set of simpler tools, which when combined with geometry decomposition leads to an adequate mesh generation process. The meshing algorithms in these tools include mapping/submapping, David R. White, “Automated Hexahedral Mesh Generation by Virtual Decomposition”, Proc. 4th Int. Meshing Roundtable, SAND95-2130, Sandia National Laboratories, Albuquerque, N. Mex. (September 1995), primitive templates, M. B. Stephenson, et al., “Using Cojoint Meshing Primitives to Generate Quadrilateral and Herxahedral Elements in Irregular Regions”, Proc. ASME Computations in Engineering Conference (1989), and sweeping or extrusion, Patrick M. Knupp, “Applications of Mesh Smoothing: Copy, Morph, and Sweep on Unstructured Quadrilateral Meshes”, Int. J. Numer. Meth. Eng., 45, 37–45 (1999). Of these, sweeping tends to be the workhorse algorithm, usually accounting for at least 50% of most meshing applications.
The sweeping algorithm involves extruding a set of quadrilaterals into a third dimension, producing a hexahedral mesh. The cross-section of the geometry being meshed can vary along the sweep direction, and the number of quadrilaterals in the set being swept can vary as well. FIG. 1 shows several sweepable geometries. Many of the commercial mesh generation software packages currently include some form of sweeping algorithm, e.g., Enterprise Software Products'FEMAP and ANSYS, Inc.'s ANSYS, and varieties of this algorithm are reported elsewhere in the literature, e.g., Patrick M. Knupp, supra; M. L. Staten, et al., “BMsweep: Locating Interior Nodes During Sweeping”, Proc. 7th Int. Meshing Roundtable, Sandia National Laboratories, Albuquerque, N. Mex. (October 1998) and T. Blacker, “The Cooper Tool”, Proc. 5th Int. Meshing Roundtable, SAND96-2301, Sandia National Laboratories, Albuquerque, N. Mex. (September 1996).
While sweeping is a widely used algorithm, it is not well automated. Before a volume can be “swept”, the algorithm must be provided with input about which surface meshes are being swept along which side surfaces, and for how far. In practice, the process of determining and specifying these source/target surfaces is user-intensive and error prone. In order to increase the level of automation in all-hexahedral meshing, an automatic method for determining sweep directions and source/target surfaces is needed.
The detection of swept features has been studied in the feature recognition community for some time, e.g., S.-S. Liu, et al., “A dual geometry—topology constraint approach for determination of pseudo-swept shapes as applied to hexahedral mesh generation”, Computer-Aided Design 31:413–426 (1999), Somashekar Subrahmanyam, et al., “An Overview of Automatic Feature Recognition Techniques for Computer-Aided Process Planning”, Computers in Industry 26:1–21 (1995), and Anshuman Razdan, et al., “Feature Based Object Decomposition for Finite Element Meshing”, The Visual Computer 5:291–303 (1989). However, the resulting algorithms are usually geometry-based, relying on arrangements such as parallel surfaces for detecting the features. These arrangements represent geometric constraints placed on extruded volumes that that are determined by the application, for example, solids to be manufactured by machining.
The present invention is of a method for detecting extruded or sweepable geometries. This method is based on topological and local geometric criteria, and is more robust than feature recognition-based algorithms. The present invention may also be used to detect extruded features for the purposes of feature extraction and disassembly planning.